#include "Histogram.h"
#include <string.h>

Histogram::Histogram(int w, int s)
{
	hsize = s;
	width = w;
	data = new int[hsize];
	for(int i = 0; i < hsize; i++)
		data[i] = 0;
	total_key_num = 0;
}

Histogram::~Histogram()
{
	if(data)
		delete [] data;
	data = NULL;
}

void Histogram::InsertKey(unsigned key)
{
	total_key_num++;
	int index = (int)(key / width);
	if(index > hsize)
		return;
	data[index]++;
}

double Histogram::RangeRatio(unsigned left, unsigned right)
{
	if (left > right)
		return 0.0;
	double sum = 0;
	int leftindex = (int)(left / width), rightindex = (int)(right / width);
	int leftmod = left % width, rightmod = right % width;
	for(int i = leftindex + 1; i < rightindex && i < hsize; i++)
		sum += data[i];
	sum += ((double)(width - leftmod)) / (double)(width) * (double)(data[leftindex]);
	if(rightindex < hsize)
		sum += ((double)rightmod / (double)(width)) * (double) (data[rightindex]);
	return sum / (double)(total_key_num);
}
